package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author By ZengPeng
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 */
public class 力扣_94_二叉树的中序遍历 {
    public static void main(String[] args) {
        TreeNode root = TreeNode.initRoot();
        List<Integer> integers = new 力扣_94_二叉树的中序遍历().inorderTraversal2(root);
        for (Integer integer : integers) {
            System.out.print(integer+",");
        }
    }

    //解法1.常规--递归法   -内存 ，速度最优
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root==null)return result;
        if(root.left!=null)
            result.addAll(inorderTraversal(root.left));
        result.add(root.val);
        if(root.right!=null)
            result.addAll(inorderTraversal(root.right));
        return result;
    }

    //解法2. while  + stack 的方式
    public  List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root==null)return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        //分析：当有比当前节点先遍历的节点，将当前节点存入stack, 下一个节点置为当前节点
        //1.有左节点时，左节点push
        //2.push 完成后 要置为空
        //3.设置遍历顺序
        while (!stack.isEmpty()) {
            TreeNode peek = stack.peek();
            if(peek.left!=null){
                stack.push(peek.left);
                peek.left =null;
                continue;
            }
            result.add(peek.val);
            stack.pop();
            if(peek.right!=null){
                stack.push(peek.right);
                peek.right=null;
            }
        }
        return result;
    }
}
